#include <stdio.h>

// 内存大小
#define MEM_SIZE 8096

// 内存块结构
typedef struct Block {
    size_t size;          // 块的大小
    struct Block* next;   // 指向下一个块的指针
} Block;

// 内存数组
char mem[MEM_SIZE];

// 内存块链表的头指针
Block* head = NULL;

// 初始化内存
void init() {
    head = (Block*)mem;
    head->size = MEM_SIZE - sizeof(Block);
    head->next = NULL;
}

// 内存申请函数
void* umalloc(size_t size) {
    Block* current = head;
    Block* prev = NULL;

    while (current != NULL) {
        if (current->size >= size) {
            // 找到了足够大的块
            if (current->size > size + sizeof(Block)) {
                // 分割块
                Block* new_block = (Block*)((char*)current + sizeof(Block) + size);
                new_block->size = current->size - size - sizeof(Block);
                new_block->next = current->next;
                current->size = size;
                current->next = new_block;
            }

            // 更新链表指针
            if (prev == NULL) {
                head = current->next;
            } else {
                prev->next = current->next;
            }

            return (char*)current + sizeof(Block);
        }

        prev = current;
        current = current->next;
    }

    // 没有足够的空间
    return NULL;
}

// 内存释放函数
void ufree(void* ptr) {
    if (ptr == NULL) {
        return;
    }

    Block* block = (Block*)((char*)ptr - sizeof(Block));
    block->next = head;
    head = block;
}

// 碎片整理函数
void umerge() {
    Block* current = head;
    Block* next;

    while (current != NULL) {
        next = current->next;

        if (next != NULL && (char*)current + sizeof(Block) + current->size == (char*)next) {
            // 合并相邻的块
            current->size += sizeof(Block) + next->size;
            current->next = next->next;
        } else {
            current = current->next;
        }
    }
}

// 打印内存状态
void printMemory() {
    Block* current = head;
    int blockNum = 0;

    while (current != NULL) {
        printf("Block %d: size=%zu\n", blockNum++, current->size);
        current = current->next;
    }
    printf("---------------\n");
}

int main() {
    // 初始化内存
    init();

    // 分配内存
    void* block1 = umalloc(1024);
    void* block2 = umalloc(2048);
    void* block3 = umalloc(512);

    // 打印内存状态
    printf("After allocation:\n");
    printMemory();

    // 释放内存
    ufree(block1);
    ufree(block3);

    // 打印内存状态
    printf("After freeing blocks 1 and 3:\n");
    printMemory();

    // 分配内存
    void* block4 = umalloc(512);

    // 打印内存状态
    printf("After allocating block 4:\n");
    printMemory();

    // 碎片整理
    umerge();

    // 打印内存状态
    printf("After merging fragments:\n");
    printMemory();

    return 0;
}